public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] nums = new int[]{};
        int[] retArr = test.searchRange(nums, 8);
        for(int x: retArr) {
            System.out.print(x + " ");
        }
    }

    public int[] searchRange(int[] nums, int target) {
        /**
         * 在排序数组中查找元素的第一个和最后一个位置*/
        // 1 预处理
        int n = nums.length;
        int[] retArray = new int[2];
        retArray[0] = -1;
        retArray[1] = -1;
        // - 处理边界
        if(n == 0) {
            return retArray;
        }

        // 2 查找左边界
        int left = 0;
        int right = n - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if(nums[left] == target) {
            retArray[0] = left;
        } else {
            return retArray;
        }

        // 3 查找右边界
        left = 0;
        right = n - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        retArray[1] = left;

        // 4 返回值
        return retArray;
    }


}
